/**
 * 最长回文子串
 * 给定一个字符串，请你找出其中最长的回文子串。
 * 当前为暴力破解，建议使用动态规划，即记录之前的子串的状态，防止重复计算。
 * 如定义boolean[][] dp表示子串是否回文
 * 如果s[i][j]相等，且boolean[i+1][j-1]为true，则该子串也为回文
 * 或者
 * dp[i]表示当前回文长度
 * 所有小的回文都是由aba组成的，所以找到第一个aba，aba之后计算dp[i]
 * 最后再遍历一遍
 * 理论上是2n
 */
class Solution {

    public static void main(String[] args) {
        System.out.println(Solution.longestPalindrome("abbabbb"));
        System.out.println(Solution.longestPalindrome("bbbaa"));
    }

    public static String longestPalindrome(String s) {
        char[] chars = s.toCharArray();
        if (chars.length == 0) {
            return "";
        }
        int start = 0;
        int end = 0;
        int max = 0;
        for (int i = 0; i < chars.length; i++) {
            //从i开始，寻找下一个和i相等的
            for (int j = i + (int) max / 2; j < chars.length; j++) {
                if (chars[i] == chars[j] && j - i >= max) {
                    //如果相等，开始处理是不是回文
                    int size = ifPalindrome(s.substring(i, j + 1));
                    if (size > max) {
                        start = i;
                        end = j;
                        max = size;
                    }
                }
            }
        }
        return s.substring(start, end + 1);
    }

    public static int ifPalindrome(String x) {
        StringBuilder sb = new StringBuilder(x);
        String reverse = sb.reverse().toString();
        if (x.equals(reverse)) {
            return x.length();
        } else {
            return -1;
        }
    }

}